package com.lun.easy;

import java.util.ArrayList;
import java.util.List;

public class CountBinarySubstrings {

	// 方法一：暴力算法，遇到超长字符串会超时
	public int countBinarySubstrings(String s) {
		int result = 0;
		// List<String> resultList = new ArrayList<>();
		for (int i = 0; i < s.length(); i++) {
			int state = 1;
			char tempChar = s.charAt(i);
			int firstCharCount = 1, secondCharCount = 0, rightPartCount = 0;
			for (int j = i + 1; j < s.length(); j++) {
				if (state == 1) {

					if (tempChar == s.charAt(j)) {
						firstCharCount++;
					} else {
						state = 2;
						tempChar = s.charAt(j);
					}
				}

				if (state == 2) {
					if (tempChar == s.charAt(j)) {
						secondCharCount++;
					}
					rightPartCount++;

					if (rightPartCount == firstCharCount) {
						if (secondCharCount == firstCharCount) {
							result++;
							// resultList.add(repeat(tempChar=='1'?'0':'1', firstCharCount) +
							// repeat(tempChar, secondCharCount));
						}
						break;
					}
				}
			}
		}

		return result;
	}

	// 方法二：
	public int countBinarySubstrings2(String s) {
		List<int[]> list = new ArrayList<>();
		int result = 0, tempIndex = 0;
		for (int i = tempIndex + 1; i <= s.length(); i++) {
			if (i == s.length() || s.charAt(i) != s.charAt(tempIndex)) {
				list.add(new int[] { tempIndex, i - 1 });
				tempIndex = i;
			}
		}

		for (int i = 0; i < list.size(); i++) {
			int[] leftPart = list.get(i);
			if (i + 1 == list.size()) {
				break;
			}
			int[] rightPart = list.get(i + 1);

			int leftSize = leftPart[1] - leftPart[0] + 1;
			int rightSize = rightPart[1] - rightPart[0] + 1;

			result += Math.min(leftSize, rightSize);
		}
		return result;
	}

	// 方法三：方法二的改进版
	public int countBinarySubstrings3(String s) {
		int result = 0, lastIndex = 0, lastSize = 0;
		for (int i = lastIndex + 1; i <= s.length(); i++) {

			if (i == s.length() || s.charAt(i) != s.charAt(lastIndex)) {

				if (lastSize == 0) {
					lastSize = i - lastIndex;
				} else {
					int currentSize = i - lastIndex;
					result += Math.min(lastSize, currentSize);
					lastSize = currentSize;
				}
				lastIndex = i;
			}

		}

		return result;
	}

	private String repeat(char c, int times) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < times; i++) {
			sb.append(c);
		}
		return sb.toString();
	}

}
